import java.util.Scanner;
/*
从左往右的尝试模型2
给定两个长度都为N的数组weights和valuesweights口和values分别代表 i号物品的重量和价值。
给定一个正数bag，表示一个载重bag的袋子你装的物品不能超过这个重量。
返回你能装下最多的价值是多少?
 */
public class Demo7 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int bag=sc.nextInt();
        int[] weight={1,6,9,4,5};
        int[] value={1,7,8,4,5};
//        int[] weight=new int[5];
//        for(int i=0;i<weight.length;i++)
//        {
//            weight[i]=sc.nextInt();
//        }
//        int[] value = new int[5];
//        for(int i=0;i<value.length;i++)
//        {
//            value[i]=sc.nextInt();
//        }

        int sum=process(weight,value,0,bag);
        System.out.println(sum);
    }

    //weight和value数组是不变的，rest是剩余位置，初始值为bag的大小，index是当前位置
    private static int process(int[] weight, int[] value, int index, int rest) {
        if(rest<0)
        {
            return -1;
        }
        if(index==weight.length)
        {
            return  0;
        }
        int p1=process(weight,value,index+1,rest);
        int p2=-1;
        int p2next=process(weight,value,index,rest-weight[index]);

        if(p2next!=-1)
        {
            p2=p2next+value[index];
        }
        return Math.max(p1,p2);
    }
}
